滑动窗口的最大值

class Solution:
    def maxInWindows(self , num: List[int], size: int) -> List[int]:
        if size == 0:
            return None
        if size > len(num):
            return None
        stack = []
        for i in range(len(num)-size+1):
            stack.append(max(num[i:i+size]))
        return stack

class Solution:
    def maxInWindows(self , num: List[int], size: int) -> List[int]:
        # write code here
        i=0
        res_list=[]
        while i+size<=len(num):
            max_value=max(num[i:i+size])
            res_list.append(max_value)
            i+=1
        return res_list

如何不超时间

class Solution:
    def maxInWindows(self , num: List[int], size: int) -> List[int]:
        # write code here
        q = []  # 构造双端队列存储单调递减的序列，q中元素为序列的索引
        res = [] # 记录结果
        for i in range(len(num)):
            # i 记录窗口右边界
            # 若 q的最大值（队头）在窗口之外，队头出队
            if len(q) != 0 and (i - q[0] + 1) > size:
                q.pop(0)
            # 将滑动到的新元素加入队尾
            while len(q) != 0 and num[i] >= num[q[-1]]:
                q.pop()
            q.append(i)
            # 当i遍历到第一个窗口的长度时，开始记录答案
            if i >= size -1:
                res.append(num[q[0]])
        return res

双端队列
时间复杂度：O(n) 空间复杂度：O(k) k为窗口大小

class Solution:
    def maxInWindows(self , num: List[int], size: int) -> List[int]:
        res = []
        dq = []
        for i in range(len(num)):
            while dq and num[dq[-1]] < num[i]:
                dq.pop()
            dq.append(i)
            if i - dq[0] >= size:
                dq.pop(0)
            if i + 1 >= size:
                res.append(num[dq[0]])
        return res

class Solution:
    def maxInWindows(self , num: List[int], size: int) -> List[int]:
        ans = []
        stack = []
        right = 0
        while right < len(num):
            val = num[right]
            while stack and right - stack[0] + 1 > size:stack.pop(0)
            while stack and num[stack[-1]] < val:stack.pop()
            stack.append(right)
            if right >= size - 1:
                ans.append(num[stack[0]])
            right += 1
        return ans

看到题目最直观的想法是：根据num和size可以确认最大值数组的规模，然后对每个窗格的最大值进行求解。然而本题有时间复杂度的要求，所以我们应该尽可能复用之前最大值的结果。

经过简单思考我们可以知道，窗格中的最大值满足以下特征：

1. 之前的最大值很可能再次成为最大值
2. 某个最大值会随着窗格离开这个最大值而无法继续成为最大值，越先成为最大值，越早失去成为最大值的资格（先进先出，满足队列的要求）
3. 窗格每次移动一个位置，新加入窗格的数字和最大值需要进行比较，如果新进入窗格的元素数值大于原来的最大值，那么原来的最大值彻底失去成为最大值的可能：有更新且更大的最大值出现

基于上述思考，我们可以得到代码

class Solution:
    def maxInWindows(self , num: List[int], size: int) -> List[int]:
        # write code here
        q = [] # store max index
        res = [] # store result
        for i in range(len(num)):
            while len(q) and i - q[0] >= size: # clear old max index
                q.pop(0)
            while len(q) and num[q[len(q) - 1]] < num[I]: # clear small max num
                q.pop()
            q.append(i)
            if i >= size - 1: # is time to get result
                res.append(num[q[0]])
        return res

class Solution:
    def maxInWindows(self , num: List[int], size: int) -> List[int]:
        # write code here
        # 不满足条件时为空
        if size==0&nbs***bsp;len(num)<size:
            return []
        # 可以生成的组数
        groups=len(num)+1-size
        res=[]
        for i in range(groups):
            # i:size+i保证每次取size个大小
            res.append(max(num[i:size+i]))
        return res

class Solution:
    def maxInWindows(self , num: List[int], size: int) -> List[int]:
        # write code here
        a=[]
        if not size:
            return a
        if len(num)<size:
            return a
        for i in range(len(num)-size+1):
            a.append(max(num[i:i+size]))
        return a